package com.likou;

import java.util.*;

public class q200 {

//    public int numIslands(char[][] grid) {
//        if (grid == null || grid.length == 0) {
//            return 0;
//        }
//
//        int gm = grid.length;
//        int gn = grid[0].length;
//
//        int ans = 0;
//        for (int i = 0; i < gm; i++) {
//            for (int j = 0; j < gn; j++) {
//                if (grid[i][j] == '1') {
//                    DFS(grid, i, j);
//                    ans++;
//                }
//            }
//        }
//
//        return ans;
//    }
//
//    private void DFS(char[][] grid, int m, int n) {
//        int gm = grid.length;
//        int gn = grid[0].length;
//
//        if (m < 0 || m > gm || n < 0 || n > gn || grid[m][n] == '0') {
//            return;
//        }
//
//        grid[m][n] = 0;
//
//        DFS(grid, m, n - 1);
//        DFS(grid, m, n + 1);
//        DFS(grid, m - 1, n);
//        DFS(grid, m + 1, n);
//    }


    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int gm = grid.length;
        int gn = grid[0].length;

        int ans = 0;
        for (int i = 0; i < gm; i++) {
            for (int j = 0; j < gn; j++) {
                if (grid[i][j] == '1') {
                    BFS(grid, i, j);
                    ans++;
                }
            }
        }

        return ans;
    }

    private void BFS(char[][] grid, int m, int n) {
        int gm = grid.length;
        int gn = grid[0].length;

        Queue<List<Integer>> queue = new LinkedList<>();
        queue.offer(List.of(m, n));
        grid[m][n] = 0;

        while (!queue.isEmpty()) {
            List<Integer> poll = queue.poll();
            Integer m1;
            Integer n1;
            // 左边
            m1 = poll.get(0);
            n1 = poll.get(1) - 1;
            if (n1 >= 0 && n1 < gn && grid[m1][n1] == '1') {
                queue.offer(List.of(m1, n1));
                grid[m1][n1] = 0;
            }

            // 右边
            m1 = poll.get(0);
            n1 = poll.get(1) + 1;
            if (n1 >= 0 && n1 < gn && grid[m1][n1] == '1') {
                queue.offer(List.of(m1, n1));
                grid[m1][n1] = 0;
            }

            // 上面
            m1 = poll.get(0) - 1;
            n1 = poll.get(1);
            if (m1 >= 0 && m1 < gm && grid[m1][n1] == '1') {
                queue.offer(List.of(m1, n1));
                grid[m1][n1] = 0;
            }

            // 下面
            m1 = poll.get(0) + 1;
            n1 = poll.get(1);
            if (m1 >= 0 && m1 < gm && grid[m1][n1] == '1') {
                queue.offer(List.of(m1, n1));
                grid[m1][n1] = 0;
            }
        }

    }
}
